package com.jhy.szl.daima20240815;

import com.jhy.suixianglu.daima20221212.ListNode;

/**
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 */
public class DetectCycle {
    public ListNode detectCycle(ListNode head) {
        // 定义快慢指针
        ListNode slow = head, fast = head;
        // 快慢指针相遇
        ListNode meet = null;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                meet = slow;
                break;
            }
        }

        if (meet == null) {
            return null;
        }
        // 重新定义一个节点指针
        ListNode temp = head;
        // 计算环的入口节点
        while (temp != meet) {
            temp = temp.next;
            meet = meet.next;
        }

        return temp;
    }
}
